package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2021-04-04 17:30
 */
public class 面试题_17_05_字母与数字 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String[] array = {"A", "B", "C"};
    System.out.println(array.length);
    String[] result = solution.findLongestSubarray(array);
    System.out.println(Arrays.toString(result));
    System.out.println(result.length);
  }

  static
  class Solution {
    public String[] findLongestSubarray(String[] array) {
      if (array == null || array.length < 2) {
        return new String[0];
      }
      Map<Integer, Integer> map = new HashMap<>();
      map.put(0, -1);
      int num = 0;
      int maxLen = 0;
      int startIndex = 0;
      for (int i = 0; i < array.length; ++i) {
        num += isDigit(array[i]) ? -1 : 1;
        if (map.containsKey(num)) {
          int preIndex = map.get(num);
          int tmpLen = i - preIndex;
          if (maxLen < tmpLen) {
            startIndex = preIndex + 1;
            maxLen = tmpLen;
          }
        } else {
          map.put(num, i);
        }
      }
      return subArray(startIndex, maxLen, array);
    }

    private String[] subArray(int startIndex, int length, String[] array) {
      String[] result = new String[length];
      for (int i = startIndex, index = 0; index < length; ++i, ++index) {
        result[index] = array[i];
      }
      return result;
    }

    private boolean isDigit(String str) {
      for (char ch : str.toCharArray()) {
        if (!Character.isDigit(ch)) {
          return false;
        }
      }
      return true;
    }

  }

  static
  class Solution_01 {
    public String[] findLongestSubarray(String[] array) {
      if (array == null || array.length < 2) {
        return new String[0];
      }
      boolean[] isDigit = new boolean[array.length];
      int num = 0;
      for (int i = 0; i < array.length; ++i) {
        if (isDigit(array[i])) {
          ++num;
          isDigit[i] = true;
        } else {
          --num;
        }
      }

      if (num == 0) {
        return array;
      }

      int maxLength = Integer.MIN_VALUE;
      int startIndex = 0;

      for (int i = 0; i < array.length; ++i) {
        int length = findLongestSubarray(i, num, isDigit);
        if (length > maxLength) {
          startIndex = i;
          maxLength = length;
        }
        if (maxLength >= array.length - i) {
          break;
        }
        num += isDigit[i] ? -1 : 1;
      }

      return subArray(startIndex, maxLength, array);
    }

    private int findLongestSubarray(int start, int num, boolean[] isDigit) {
      int right = isDigit.length - 1;
      while (num != 0 && right > start) {
        num += isDigit[right] ? -1 : 1;
        --right;
      }

      if (num != 0) {
        return 0;
      }
      return right - start + 1;
    }

    private String[] subArray(int startIndex, int length, String[] arr) {
      String[] result = new String[length];
      for (int i = startIndex, index = 0; index < length; ++i, ++index) {
        result[index] = arr[i];
      }
      return result;
    }

    private boolean isDigit(String str) {
      for (char ch : str.toCharArray()) {
        if (!Character.isDigit(ch)) {
          return false;
        }
      }
      return true;
    }
  }

}
